#include <stdio.h>
#include <stdlib.h>

typedef struct Node_ {
  int data;
  struct Node_ *next;
} Node;

/* recursive */
Node *reverse_r(Node *head) {
  if (NULL == head) return head;
  if (NULL == head->next) return head;
  Node *ph = reverse_r(head->next);
  head->next->next = head;
  head->next = NULL;
  return ph;
}

/* without recursive */
Node *reverse(Node *head) {
  Node *p = head;
  Node *previous = NULL;
  if (NULL == head) return head;
  while (p->next != NULL) {
    p = p->next;
    head->next = previous;
    previous = head;
    head = p;
  }
  head->next = previous;

  return head;
}

static void print_list(Node *head) {
  int i;
  Node *p;
  printf("list: ");
  for (i = 0, p = head; i < 15 && p != NULL; p = p->next, ++i) {
    printf("%d -> ", p->data);
  }
  printf("\n");
}

static void free_list(Node *head) {
  Node *p;
  int i;
  
  if (NULL == head)
    return;
  
  for (i = 0; i < 10; ++i) {
    p = head;
    head = head->next;
    free(p);
  }
}

static Node *list_create(Node *h1) {
  Node *p;
  int a1[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
  int i;
  
  for (h1 = NULL, i = 10; i > 0; --i) {
    p = (Node *)malloc(sizeof(Node));
    if (NULL == p)
      return NULL;

    p->next = h1;
    p->data = a1[i-1];
    h1 = p;
  }
  return h1;
}

void test1() {
  Node *head = NULL;
  head = list_create(head);
  print_list(head);
  head = reverse_r(head);
  print_list(head);
  free_list(head);
}

void test2() {
  Node *head = NULL;
  head = list_create(head);
  print_list(head);
  head = reverse(head);
  print_list(head);
  free_list(head);
}

int main() {
  test1();
  test2();
  
  return 0;
}
